"""
有效括号字符串需满足：
* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。
* 注意空字符串可被认为是有效字符串。

举例：

((())): True

((()): False

(())): False
"""


class Stack(object):
    def __init__(self, limit):
        self.stack = []  # 定义一个列表用来存放元素
        self.limit = limit  # 定义栈的容量极限

    # 进栈
    def push(self, data):
        # 判断栈是否溢出
        if len(self.stack) >= self.limit:
            raise IndexError("超出栈容量限制")
        self.stack.append(data)

    # 出栈
    def pop(self):
        # 判断是否为空栈
        if self.stack:
            return self.stack.pop()
        else:
            raise IndexError("空栈不能弹出")

    # 查看栈顶的元素
    def peek(self):
        # 判断是否为空栈
        if self.stack:
            return self.stack[-1]

    # 是空栈吗?
    def is_empty(self):
        return not bool(self.stack)

    # 栈的大小
    def size(self):
        return len(self.stack)


def balanced_parentheses(parentheses):
    stack = Stack(len(parentheses))
    for parenthesis in parentheses:
        # 碰到左括号( 就把(压入栈
        if parenthesis == '(':
            stack.push(parenthesis)
        # 碰到右括号) 就出栈一个元素
        elif parenthesis == ')':
            # 如果是空栈, 说明括号使用顺序不对
            if stack.is_empty():
                return False
            stack.pop()
    # 循环执行完毕判断栈是否为空栈
    # 空栈: 左右括号数量匹配 -- True
    # 不是空栈: 说明左右括号数量不匹配 -- False
    return stack.is_empty()


if __name__ == '__main__':
    examples = ['((()))', '((())', '(()))']
    print('Balanced parentheses demonstration:\n')
    for example in examples:
        print(example + ': ' + str(balanced_parentheses(example)))
